package com.lw.leetcode.str.b;

import java.util.*;

/**
 * 767. 重构字符串
 *
 * @Author liw
 * @Date 2021/7/6 14:48
 * @Version 1.0
 */
public class ReorganizeString {

    public static void main(String[] args) {
        ReorganizeString test = new ReorganizeString();
        String str = "aaabbcccccc";
//        String str = "abbabbaaab";
//        String str = "vvvlo";
        String string = test.reorganizeString(str);
        System.out.println(string);
    }

    public String reorganizeString(String s) {
        int length = s.length();
        char[] chars = s.toCharArray();
        int[] arr = new int[26];
        for (char c : chars) {
            arr[c - 97] += 1;
        }
        int l = (length + 1) >> 1;
        for (int i : arr) {
            if (i > l) {
                return "";
            }
        }
        int index = 0;
        Map<Integer, List<Character>> map = new TreeMap<>((a, b) -> b - a);

        for (int i = 0; i < 26; i++) {
            int count = arr[i];
            char c = (char) (i + 97);
            if (count != 0) {
                List<Character> list = map.get(count);
                if (list == null) {
                    list = new ArrayList<>();
                    list.add(c);
                    map.put(count, list);
                } else {
                    list.add(c);
                }
            }
        }
        for (Map.Entry<Integer, List<Character>> entry : map.entrySet()) {
            for (Character c : entry.getValue()) {
                int count = entry.getKey();
                while (count > 0) {
                    chars[index] = c;
                    index = index + 2 >= length ? 1 : index + 2;
                    count--;
                }
            }

        }

        return String.valueOf(chars);
    }

}
